package codeTop;

import java.util.Arrays;

public class q31 {
    public void nextPermutation(int[] nums) {
        int idx1 = -1;
        for (int i = nums.length-1; i >0; i--) {
            if (nums[i]>nums[i-1]){
                idx1 = i-1;
                break;
            }
        }
        if (idx1 == -1) {
            reverse(nums,0, nums.length-1);
            return;
        }
        int idx2 = idx1+1;
        while (idx2 < nums.length) {
            if (nums[idx2]<=nums[idx1]){
                break;
            }
            idx2++;
        }
        idx2--;
        swap(nums,idx1,idx2);
        reverse(nums,idx1+1, nums.length-1);
    }
    void reverse(int[] nums,int start,int end){
        for (int i = 0; i <(end-start+1)/2 ; i++) {
            swap(nums,start+i,end-i);
        }
    }
    void swap(int[] nums,int idx1,int idx2){
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }

    public static void main(String[] args) {
        q31 q = new q31();
        q.nextPermutation(new int[]{3,2,1});
    }
}
